#include <iostream>
#include <vector>
using namespace std;
struct Node{
    int value;
    Node *next;
    Node(int x=0,Node *pt=nullptr):value(x),next(pt){}
};
void pritList(Node *head){
    if(head==nullptr) return;
     while(head){
            cout << head->value << " ";
            head=head->next;
       }
    cout <<endl;
}
Node* mergeTowList(Node* l1,Node *l2){
    Node *new_list=new Node;
    Node *r=new_list;
    while(l1&&l2){
        if(l1->value < l2->value){
            new_list->next=l1;
            l1=l1->next;
        }else{
            new_list->next=l2;
            l2=l2->next;
        }
        new_list=new_list->next;
    }
    if(l1){
        new_list->next=l1;
    }
    if(l2){
        new_list->next=l2;
    }

    return r->next;
}

Node* mergeNodeList(vector<Node*> &node_list){
    Node *head=new Node;
    int len=node_list.size();
    if(len==0){
        delete head;
        return head->next;
    }else if(1==len){
        delete head;
        return node_list[0];
    }else if(2==len){
        delete head;
        return mergeTowList(node_list[0],node_list[1]);
    }
    auto it=node_list.begin();
    while(it!=node_list.end()){
        Node *l_head=(*it);
        head->next=mergeTowList(head->next,l_head);
        
        it++;
    }
    
    Node *h=head->next;
    delete head;
    return h;
}

Node* BuildList(vector<int> &v){
    Node *node=new Node;
    Node *tode=node;
    for(auto x:v){
        Node *tnode=new Node(x,nullptr);
        tode->next=tnode;
        tode=tode->next;
    }
    return node->next;
}

int main() {
    vector<vector<int>> v={
        {1,5,7},
        {2,11,20},
        {3,6,9}
    };
    vector<Node*> vv;
    for(auto x:v){
        Node *n=BuildList(x);
        //pritList(n);
        vv.push_back(n);
    }
    
//     for(auto x:vv){
//         pritList(x);
//     }
   // Node *head=mergeTowList(vv[0],vv[1]);
    Node *head=mergeNodeList(vv);
    //Node *head=vv[0];
   pritList(head);
    //int a;
    //cin >> a;
   // cout << "Hello World!" << endl;
}